package graph.directed.kosaraju.connectedComponent;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import graph.unweighted.CandyGraph;
import graph.unweighted.dfs.CandyDFS;

/**
 * 
 * @Title: CandyDFS.java 
 * @Package graph.dfs 
 * @Description: 使用kosaraju算法求解有向图的强连通分量
 * @author CandyWall   
 * @date 2021年1月14日 下午7:48:11 
 * @version V1.0
 */
public class CandyStronglyConnectedComponent {
    private CandyGraph graph;
    private int[] visited;  //记录顶点是否被遍历过，默认都为false
    private int stronglyConnectedComponentCount = 0;
    public CandyStronglyConnectedComponent(CandyGraph graph) {
        if(!graph.isDirected()) {
            throw new IllegalArgumentException("该类只能检测有向图中强连通分量的个数！");
        }
        this.graph = graph;
        visited = new int[graph.getVertex_num()];
        Arrays.fill(visited, -1);
        // 将当前有向图的反图，即将图中所有边的方向逆序，获取深度优先遍历的后序序列
        CandyDFS dfs = new CandyDFS(graph.reverseGraph());
        ArrayList<Integer> postOrderList = dfs.getPostOrderList();
        // 后序序列再去逆序列
        Collections.reverse(postOrderList);
        // 通过深度优先遍历的方法求联通分量
        // 同一个连通分量中的顶点的visited[v]的值相等，即连通分量分组编号相等
        for(int v : postOrderList) {
            if(visited[v] == -1) {
                dfs(v, stronglyConnectedComponentCount);
                stronglyConnectedComponentCount++;
            }
        }
    }

    /**
     * 深度优先遍历
     * @param v：顶点编号
     * @param stronglyConnectedComponentId：连通分量编号
     */
    private void dfs(int v, int stronglyConnectedComponentId) {
        visited[v] = stronglyConnectedComponentId;
        for(int w : graph.adjacentVertexes(v)) {
            if(visited[w] == -1) {
                dfs(w, stronglyConnectedComponentId);
            }
        }
    }
    
    /**
     * 获取图中强连通分量的个数
     * @return
     */
    public int getStronglyConnectedComponentCount() {
        return stronglyConnectedComponentCount;
    }
    
    /**
     * 获取所有的连通分量，每个集合中保存相应连通分量中的元素
     */
    public ArrayList<Integer>[] getConnectedComponents() {
        ArrayList<Integer>[] res = new ArrayList[stronglyConnectedComponentCount];
        for(int i = 0; i < stronglyConnectedComponentCount; i++) {
            res[i] = new ArrayList<Integer>();
        }
        for(int v = 0; v < visited.length; v++) {
            res[visited[v]].add(v);
        }
        return res;
    }

    /**
     * 判断两个顶点是否连接，即是否在同一个连通分量中
     * @param v
     * @param w
     * @return
     */
    public boolean isStronglyConnected(int v, int w) {
        graph.validateVertex(v);
        graph.validateVertex(w);
        return visited[v] == visited[w];
    }

    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/directed/kosaraju/Graph1.txt", true);
        CandyStronglyConnectedComponent scc = new CandyStronglyConnectedComponent(graph);
        System.out.println("强连通分量的个数为：" + scc.getStronglyConnectedComponentCount());
        System.out.print("强连通分量为：");
        System.out.println(Arrays.toString(scc.getConnectedComponents()));
    }
}
